package sort;

import java.util.*;

/**
 * 排序
 *
 * @author miweidong
 * @date 2021-09-26 11:28
 */
public class Sort {
    public static void main(String[] args) {
        int[] arr = {144, 4, 6, 5, 3, 2, 6, 7, 8, 0, 123, 132, 154, 1000};
        //bubbleSort(arr);
        //selectionSort(arr);
        //insertSort(arr);
        //shellSort(arr);
        //mergeSort(arr);
        //quickSort(arr);
        //heapSort(arr);
        //countingSort(arr);
        //bucketSort(arr);
        radixSort(arr);
    }


    /**
     * 冒泡排序
     *
     * @param arr 排序数组
     */
    public static void bubbleSort(int[] arr) {
        // i < arr.length - 1  最后一个不用排
        for (int i = 0; i < arr.length - 1; i++) {
            // j < arr.length - 1 - i  防止越界，每次少排一个
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // swap
                    int temp;
                    temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 选择排序
     * 在已知序列中，每次找到最小或最大的，与当前索引的值进行交换
     *
     * @param arr 排序数组
     */
    public static void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int index = i;
            int min = arr[i];
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < min) {
                    min = arr[j];
                    index = j;
                }
            }
            // swap
            int temp;
            temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 插入排序
     * 在已排序的序列中，每次从未排序的序列中获取一个，从右往左找到对应位置插入
     *
     * @param arr 排序数组
     */
    public static void insertSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int preIndex = i;
            int current = arr[i + 1];
            // 移动位置，且记录要插入位置索引
            while (preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 希尔排序 O(n^2)  ----  缩小增量排序
     * 优先比较距离较远的元素，按步长进行相邻间隔排序，最后步长是1，做冒泡就可以
     *
     * @param arr 排序数组
     */
    public static void shellSort(int[] arr) {
        int length = arr.length;
        int half = 2;
        for (int gap = length / half; gap > 0; gap /= half) {
            for (int j = gap; j < length; j++) {
                int k = j;
                int current = arr[j];
                while (k - gap >= 0 && current < arr[k - gap]) {
                    arr[k] = arr[k - gap];
                    k = k - gap;
                }
                arr[k] = current;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 归并排序
     * 分治思想，相同子问题，拆到最小粒度，计算粒度，然后合并，归约出答案
     *
     * @param arr 排序数组
     */
    public static void mergeSort(int[] arr) {
        int[] temp = new int[arr.length];
        System.out.println("合并过程如下：");
        mergeSortRecursion(arr, 0, arr.length - 1, temp);
        System.out.println("归并后最终结果：" + Arrays.toString(temp));
    }

    /**
     * 归并递归方法
     * 出口是数组不可再分，开始索引left > 最后索引right 不再分
     *
     * @param arr   排序数组
     * @param left  开始索引
     * @param right 结束索引
     * @param temp  临时数组
     */
    public static void mergeSortRecursion(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int middle = (left + right) / 2;
            // 分左边
            mergeSortRecursion(arr, left, middle, temp);
            // 分右边
            mergeSortRecursion(arr, middle + 1, right, temp);
            // 合并两个有序序列
            mergeSerializer(arr, left, middle, right, temp);
        }
    }

    /**
     * 合并有序序列
     */
    public static void mergeSerializer(int[] arr, int left, int middle, int right, int[] temp) {
        System.out.println("归并索引:" + left + " " + middle + " " + right);
        // 左序列索引
        int i = left;
        // 右序列索引
        int j = middle + 1;
        // 临时数组索引
        int t = 0;
        while (i <= middle && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= middle) {
            temp[t++] = arr[i++];
        }
        while (j <= right) {
            temp[t++] = arr[j++];
        }
        t = 0;
        while (left <= right) {
            arr[left++] = temp[t++];
        }
        System.out.println(Arrays.toString(temp));
    }

    /**
     * 快速排序
     * <p>
     * 选择一个基准数，同时左右扫描，将数组以基准数为中心，分割为两个部分，一部分比基准数大，一部分比基准数小
     * 先交换，后分区
     * <p/>
     *
     * @param arr 排序数组
     */
    public static void quickSort(int[] arr) {
        quickSortRecursion(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 快速排序递归方法
     *
     * @param arr   排序数组
     * @param left  起始索引
     * @param right 结束索引
     */
    public static void quickSortRecursion(int[] arr, int left, int right) {
        if (left < right) {
            int middle = quickSortSwap(arr, left, right);
            quickSortRecursion(arr, left, middle - 1);
            quickSortRecursion(arr, middle + 1, right);
        }
    }

    /**
     * 扫描交换位置
     * <p>
     * 将第一个数用临时变量存储起来，i 指向第一个数位置索引 ， j 指向最后一个位置
     * 注意：要先从左扫描
     * 从左扫描比基准数小的，赋值给 i
     * 从右往左扫描比基准数大的， 赋值给 j
     * 如果i 和 j 相遇，将基准数赋值给当前i 索引
     * 返回索引 i ，表示下次交换的两部分的结束索引（i-1）和 开始索引（i+1）
     * </p>
     *
     * @param arr   排序数组
     * @param left  起始索引
     * @param right 结束索引
     * @return 以第一个数为基准的左右有序
     */
    public static int quickSortSwap(int[] arr, int left, int right) {
        int i = left;
        int j = right;
        int temp = arr[i];
        while (i < j) {
            while (i < j && temp <= arr[j]) {
                j--;
            }
            arr[i] = arr[j];
            while (i < j && temp >= arr[i]) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = temp;
        return i;
    }

    /**
     * 堆排序
     * <p>
     * 利用堆这种数据结构来排序;
     * 堆积是一种近似完全二叉树的结构
     * 完全二叉树： 首先是二叉树，其次所有节点从上往下，从左往右紧密排列（单个叶子节点允许，但不允许跨过一个节点，给其兄弟节点加个叶子节点）
     * 我们依次从上往下，从左往右给完全二叉树从索引0开始编码，从而可以看出完全二叉树的性质：
     * i -> 当前完全二叉树节点数
     * 则  parent = (i - 1) / 2;
     * leftChild = 2i + 1;
     * rightChild = 2i + 2;
     * 堆积性质：子节点的键值或索引总是小于或大于它的父节点
     * 小根堆：k(i) <= k(2i) && k(i) <= k(2i+1)
     * 大根堆：k(i) >= k(2i) && k(i) >= k(2i+1)
     * </p>
     *
     * @param arr 排序数组
     */
    public static void heapSort(int[] arr) {
        // 用数组来表示树结构
        // n 指的是树中的节点数
        buildHeap(arr, arr.length);
        for (int i = arr.length - 1; i >= 0; i--) {
            // 将构建好的堆中的根节点和最后一个节点交换，砍掉最后一个节点
            heapSwap(arr, i, 0);
            heapify(arr, i, 0);
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 对堆中的某个节点进行重构，使其满足堆结构
     *
     * @param arr     完全二叉树
     * @param n       所有节点数
     * @param current 重构节点索引
     */
    public static void heapify(int[] arr, int n, int current) {
        if (n <= current) {
            return;
        }
        int leftChild = 2 * current + 1;
        int rightChild = 2 * current + 2;
        int max = current;
        if (leftChild < n && arr[leftChild] >= arr[max]) {
            max = leftChild;
        }
        if (rightChild < n && arr[rightChild] > arr[max]) {
            max = rightChild;
        }
        // 如果本身最大，则不需要交换
        if (max != current) {
            heapSwap(arr, max, current);
            heapify(arr, n, max);
        }

    }

    /**
     * 堆交换函数
     *
     * @param arr 完全二叉树
     * @param i   父节点
     * @param j   最大节点
     */
    public static void heapSwap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 构建堆
     *
     * @param arr 乱序数组
     * @param n   节点数
     */
    public static void buildHeap(int[] arr, int n) {
        int lastNode = n - 1;
        int parent = (lastNode - 1) / 2;
        for (int i = parent; i >= 0; i--) {
            heapify(arr, n, i);
        }
    }


    /**
     * 计数排序
     * <p>
     * 查找到原始数组中的最大值和最小值，
     * 申请 max - min + 1 个空间，当作计数数组
     * 遍历原始数组，当原始数组中的value与计数数组中的索引相同时，计数数组索引位置++
     * 遍历计数数组，索引为原始数组的value,值为该数重复次数
     * 当然，计数排序还有其他延申算法，后续再说
     * </p>
     *
     * @param arr 排序数组
     */
    public static void countingSort(int[] arr) {
        int min = arr[0];
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (min > arr[i]) {
                min = arr[i];
            }
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        // max - min + 1  节省空间
        int[] newArr = new int[max - min + 1];
        for (int value : arr) {
            newArr[value - min]++;
        }
        int index = 0;
        for (int i = 0; i < newArr.length; i++) {
            int j = newArr[i];
            while (j != 0) {
                arr[index++] = i + min;
                j--;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 桶排序
     *
     * <p>
     * 过于粗糙 ！！！！！！！！！
     * 把数据放入桶里，桶间可存储数据范围连续顺序递增，桶内自动排序
     * 最终以桶的顺序，从小到大扫描桶内数据
     * </p>
     *
     * @param arr 排序数组
     */
    public static void bucketSort(int[] arr) {
        List<LinkedList<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < 2; i++) {
            buckets.add(new LinkedList<>());
        }
        for (int value : arr) {
            if (value >= 0 && value <= 5) {
                buckets.get(0).add(value);
                bucketInsertSort(buckets.get(0));
            } else {
                buckets.get(1).add(value);
                bucketInsertSort(buckets.get(1));
            }
        }
        int index = 0;
        for (LinkedList<Integer> bucket : buckets) {
            for (Integer value : bucket) {
                arr[index++] = value;
            }
        }
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 桶内排序
     *
     * @param bucketList 桶内链表
     */
    public static void bucketInsertSort(LinkedList<Integer> bucketList) {
        bucketList.sort(Comparator.comparingInt(a -> a));
    }


    /**
     * 基数排序
     * 是以数字的个位、十位、百位、千位、、、、、、进行排序
     *
     * @param arr 排序数组
     */
    public static void radixSort(int[] arr) {
        List<LinkedList<Integer>> buckets = new ArrayList<>();
        // 必须创建10个桶，十进制数字为0~9
        for (int i = 0; i < 10; i++) {
            buckets.add(new LinkedList<>());
        }
        // 找到最大的数
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        // 判断这个数是几位
        int count = 1;
        int k = 10;
        while (max / k != 0) {
            count++;
            k *= 10;
        }
        int m = 1;
        for (int i = 0; i < count; i++) {
            for (int item : arr) {
                buckets.get(item / m % 10).add(item);
                bucketInsertSort(buckets.get(item / m % 10));
            }
            System.out.println(buckets);
            int index = 0;
            for (LinkedList<Integer> bucket : buckets) {
                for (Integer value : bucket) {
                    arr[index++] = value;
                }
            }
            buckets.forEach(LinkedList::clear);
            System.out.println(Arrays.toString(arr));
            m *= 10;
        }
        System.out.println(Arrays.toString(arr));
    }
}
